#include <iostream>
#include <list>
#include <map>

using namespace std;

class LRUCache
{
private:
    int count = 0;
    int capacity;
    list<int> time_record;
    map<int, std::pair<int, list<int>::iterator>> cache;

public:
    LRUCache(int capacity)
    {
        this->capacity = capacity;
    }

    int get(int key)
    {
        if (cache.find(key) == cache.end())
        {
            return -1;
        }
        else
        {
            time_record.erase(cache[key].second);
            time_record.push_front(key);
            cache[key].second = time_record.begin();
            return cache[key].first;
        }
    }

    void put(int key, int value)
    {
        if (cache.find(key) == cache.end())
        {
            time_record.push_front(key);
            cache[key] = make_pair(value, time_record.begin());
            count++;
        }
        else
        {
            cache[key].first = value;
            time_record.erase(cache[key].second);
            time_record.push_front(key);
            cache[key].second = time_record.begin();
        }
        if (count > capacity)
        {
            cache.erase(time_record.back());
            time_record.pop_back();
            count--;
        }
    }
};

int main()
{
    cout << "Code146" << endl;
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // returns 1
    cache.put(3, 3); // evicts key 2
    return 0;
}